package com.zhupf.stack;

import java.util.Arrays;
import java.util.Deque;
import java.util.LinkedList;

/**
 * @author zhupf
 * @date 2024年12月13日 9:27 有空再做
 * @Description https://leetcode.cn/problems/create-maximum-number/description/
 * 321. 拼接最大数
 * 给你两个整数数组 nums1 和 nums2，它们的长度分别为 m 和 n。数组 nums1 和 nums2 分别代表两个数各位上的数字。同时你也会得到一个整数 k。
 * <p>
 * 请你利用这两个数组中的数字中创建一个长度为 k <= m + n 的最大数，在这个必须保留来自同一数组的数字的相对顺序。
 * <p>
 * 返回代表答案的长度为 k 的数组。
 * <p>
 * 示例 1：
 * <p>
 * 输入：nums1 = [3,4,6,5], nums2 = [9,1,2,5,8,3], k = 5
 * 输出：[9,8,6,5,3]
 * 示例 2：
 * <p>
 * 输入：nums1 = [6,7], nums2 = [6,0,4], k = 5
 * 输出：[6,7,6,0,4]
 * 示例 3：
 * <p>
 * 输入：nums1 = [3,9], nums2 = [8,9], k = 3
 * 输出：[9,8,9]
 */
public class MaxNumber {

    public static void main(String[] args) {
        int[] nums1 = {3, 4, 6, 5};
        int[] nums2 = {9, 1, 2, 5, 8, 3};
        MaxNumber maxNumber = new MaxNumber();
        System.out.println(Arrays.toString(maxNumber.maxNumber(nums1, nums2, 5)));
    }


    public int[] maxNumber(int[] nums1, int[] nums2, int k) {
        int[] maxNum = new int[k];
        int start = nums2.length >= k ? 0 : k - nums2.length;
        int end = Math.min(nums1.length, k);
        for (int i = start; i <= end; i++) {
            int[] res = mergeMaxNums(removeKdigits(nums1, i), removeKdigits(nums2, k - i));
            for (int j = 0; j < k; j++) {
                if (res[j] == maxNum[j]) {
                    continue;
                }
                maxNum = res[j] > maxNum[j] ? res : maxNum;
                break;
            }
        }
        return maxNum;
    }

    public int[] removeKdigits(int[] nums, int k) {
        if (k == 0) {
            return null;
        }
        int len = nums.length;
        int[] res = new int[k];
        int remve = len - k;
        Deque<Integer> deque = new LinkedList<>();
        for (int i = 0; i < len; i++) {
            while (!deque.isEmpty() && remve > 0 && nums[deque.peek()] < nums[i]) {
                deque.pop();
                remve--;
            }
            deque.push(i);
        }

        for (int i = 0; i < k; i++) {
            res[i] = nums[deque.pollLast()];
        }
        return res;
    }

    public int[] mergeMaxNums(int[] nums1, int[] nums2) {
        if (nums1 == null) {
            return nums2;
        }
        if (nums2 == null) {
            return nums1;
        }
        int[] res = new int[nums1.length + nums2.length];
        int idx1 = 0;
        int idx2 = 0;
        for (int i = 0; i < res.length; i++) {
            if (compar(nums1, idx1, nums2, idx2) > 0) {
                res[i] = nums1[idx1++];
            } else {
                res[i] = nums2[idx2++];
            }
        }

        return res;
    }

    public int compar(int[] nums1, int idx1, int[] nums2, int idx2) {
        while (idx1 < nums1.length && idx2 < nums2.length) {
            int diff = nums1[idx1] - nums2[idx2];
            if (diff != 0) {
                return diff;
            }
            idx1++;
            idx2++;
        }
        return (nums1.length - idx1) - (nums2.length - idx2);
    }

}
